The present invention relates to modulus calculations. In particular, it relates to modulus calculations that may be performed with high degrees of efficiency.
A modulus calculation (colloquially, a “mod” calculation) determines the remainder of a division operation. Thus, the expression A mod N determines a result that is the remainder obtained by dividing the number A by N. Example: 17 divided by 3 is 5 with a remainder of 2. “17 mod 3” yields a result having value 2.
Mod calculations are performed in many computing applications including key negotiation conducted between two parties before engaging in encrypted communication. In the key negotiation context, evaluation of equations having the form (AB) mod n is performed at two terminals. Often, the A and B values may be quite large—from 1024 to 2048 bits long. Of course, when two operands having length l are multiplied, the result may have a length of up to 2l. With such large operands, it is impractical to build result registers in a processor that have the full width of the multiplication result. Instead, as multiplication results are generated, they typically are truncated by applying the mod calculation to each product. Because the mod calculation divides each product by a modulus having its own length (say, j), the result always has a length less than j.
Assuming operands of length l and an equal number of 0s and 1s therein, evaluation of AB mod n may require l multiplications and l mod operations. This involves considerable computational expense. The expense associated with such computations becomes particularly severe in high-load environments such as computer servers where it can be expected that several thousand key negotiation requests (maybe more) would be received per hour.
Accordingly, there is a need in the art for a fast, computationally inexpensive technique for resolving mod operations with large operands.